Public key cryptography is a technique for protecting communications. Using this technique, electronic devices wishing to transmit information amongst themselves are each associated with a public key and a private key. Each electronic device's private key is kept by that electronic device as a secret from all other electronic devices. Each electronic device's public key may be widely distributed amongst other electronic devices. Each corresponding public key and private key are related mathematically, but the private key cannot be practically derived from the public key. In use, for example, a first electronic device wishing to send a cryptographically processed message to a second electronic device first encrypts the message with the second electronic device's public key. The first electronic device then forwards the cryptographically processed message to the second electronic device. Upon receiving the cryptographically processed message, the second electronic device decrypts the message with the second electronic device's private key.
One conventional way of creating and using public and private keys is through the use of Elliptic Curve Cryptography (ECC). ECC incorporates a group of points on an elliptic curve defined over a finite field in the production of public and private keys. ECC is useful for defining the relationship between public and private keys because there is no sub-exponential algorithm known to solve a discrete logarithm problem on a properly chosen elliptic curve. The lack of such a known algorithm ensures that a private key cannot be practically derived from its corresponding public key. The performance of ECC depends on the speed of finite field operations and scalar multiplication, and the choice of curve and finite field. While there is a standard type of elliptic curve equation, there are many different elliptic curves. They are distinguished by the values of their coefficients and the finite field over which they are defined.
Curves in common use are standardized by organizations such as the National Institute of Standards and Technology (NIST) and the American National Standards Institute (ANSI). These standardized curves are given names and are referred to as named curves. Despite being called named curves, they actually define an elliptic curve group. An elliptic curve group is defined by an operation that can be applied to points on an elliptic curve, referred to as point addition, together with a set of points on the curve. This set of points is defined such that, given a point on the elliptic curve (i.e., a base point, or a generator point), all points in the set can be obtained by successive application of the point addition operation to the base point. The elliptic curve group includes the point at infinity which is the additive identity of the group. The number of points in the elliptic curve group is called the order. An example named curve is P256, which is defined in NIST's Digital Signature Standard issued on Jan. 27, 2000 as FIPS 186-2, the contents and teachings of which are hereby incorporated by reference in their entirety. Other examples of named curves include B283, K283, B409, K409, P384, B571, K571, and P521.
ECC scalar multiplication is the multiplication of a point on the elliptic curve by a scalar. While ECC scalar multiplication can be described in terms of successively applying point addition, there are techniques available that allow a scalar multiplication to be performed more quickly. ECC scalar multiplication can be accelerated by pre-generating multiples of the point to be multiplied. This set of pre-generated values is called an acceleration table. Acceleration tables are made up of sub-tables, each sub-table being used to calculate a partial result for a sub-set window size bits in length of the scalar.